<?php
/**
 * 以SVG的形式输出二叉树
 */
class BinaryTreeSVG
{
    /**
     * @var array[] $map 二位数组，内部是二叉树节点
     */
    public $map=[];
    /**
     * @param BinaryNode $root 根节点
     * @param float $min_space 横向的元素之间的最小间隔
     * @param float $floor_height 两层之间的间隔
     * @param float $radius 元素半径
     * @param float $line_width 线宽
     */
    public function fetch($node,$min_space,$floor_height,$radius,$line_width,$text_x=-10,$text_y=5)
    {
        $this->map=[];
        $this->min_space=$min_space;
        $this->floor_height=$floor_height;
        $this->tidy($node,0);
        list($min_x,$max_x)=$this->compute();
        $width = $max_x - $min_x + 2 * $min_space;
        $height = (count($this->map) + 1) * $floor_height;

        $this->xo = -$min_x + $min_space;//x轴上的偏移量
        $this->node_postfix='r="'.$radius.'" stroke="black" stroke-width="'.$line_width.'" fill="white"/>'."\r\n";
        $this->line_postfix='style="stroke:rgb(0,0,0);stroke-width:'.$line_width.'"/>'."\r\n";
        $this->line_svg = $this->node_svg = $this->text_svg = "";
        $this->text_x = $text_x;
        $this->text_y = $text_y;
        $this->fetch_node($node,$floor_height);

        $output='<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="'.$width.'" height="'.$height.'" version="1.1" xmlns="http://www.w3.org/2000/svg">'."\r\n".
$this->line_svg."\r\n".
$this->node_svg."\r\n".
$this->text_svg.'</svg>'."\r\n";
        return $output;
    }
    /**
     * 整理节点
     * 先序遍历二叉树，将节点分层放到二维数组$map里
     * @param BinaryNode $node
     */
    public function tidy($node,$floor)
    {
        if(!isset($this->map[$floor])){
            $this->map[$floor]=[];
        }
        $index=count($this->map[$floor]);
        $this->map[$floor][]=$node;
        $node->floor=$floor;
        $node->index=$index;
        $node->x=NAN;
        if($node->left !== null) $this->tidy($node->left,$floor+1);
        if($node->right !== null) $this->tidy($node->right,$floor+1);
    }
    /**
     * 递归的移动节点和其下级节点(只能向右)
     */
    public function moveNode($node,$dx,$move_next=false)
    {
        if($dx < 0){
            throw new Exception();
        }
        $node->x += $dx;
        if($node->left !== null) $this->moveNode($node->left,$dx);
        if($node->right !== null) $this->moveNode($node->right,$dx);
        if($move_next){
            $line=$this->map[$node->floor];
            $count=count($line);
            for($i=$node->index+1; $i<$count; $i++){
                $this->moveNode($line[$i],$dx);
            }
        }
    }
    /**
     * 计算x坐标
     * 从下向上遍历$map
     * 以第一个节点为原点计算x坐标,向右为正方向
     * 比较每层左右两边的最大距离(用来计算整体偏移量)
     */
    public function compute()
    {
        /** @var BinaryNode $node*/
        $floor=count($this->map)-1;
        $line=$this->map[$floor];
        foreach($line as $index => $node){
            $node->x = $index * $this->min_space;
        }
        for($i=$floor-1; $i>=0; $i--){
            $this->computeLine($this->map[$i]);
        }
        //获取最大最小边界
        $min_x = $max_x = 0;
        for($i=$floor; $i>=0; $i--){
            $line=$this->map[$i];
            if($min_x > $line[0]->x){
                $min_x = $line[0]->x;
            }
            if($max_x < $line[count($line)-1]->x){
                $max_x = $line[count($line)-1]->x;
            }
        }
        return [$min_x,$max_x];
    }
    public $change=false;
    /**
     * 计算某一行上的节点的x坐标(除了最底层的一行)
     */
    public function computeLine($line)
    {
        //如果节点有子节点，则使用子节点确定坐标
        foreach($line as $node){
            if($node->left){
                if($node->right)    $x = ($node->left->x + $node->right->x)/2;
                else                $x = $node->left->x + $this->min_space/2;
            }
            else{
                if($node->right)    $x = $node->right->x - $this->min_space/2;
                else                $x = NAN;
            }
            $node->x=$x;
        }

        //遍历一遍，查找未确定的节点，并且赋值
        $start=null;
        $end=null;
        $unknow=[];
        foreach($line as $node){
            if(is_nan($node->x)){
                $unknow[]=$node;
            }
            else{
                $end=$node;
                if($start === null){
                    foreach($unknow as $unknown_node){
                        $unknown_node->x = $end->x - ($end->index - $unknown_node->index) * $this->min_space;
                    }
                }
                else{
                    $total_min_space=($end->index - $start->index) * $this->min_space;
                    if(($end->x - $start->x) < $total_min_space){
                        $this->moveNode($end , $total_min_space + $start->x - $end->x , true);
                    }
                    foreach($unknow as $unknown_node){
                        $unknown_node->x = ($unknown_node->index - $start->index) * $this->min_space + $start->x;
                    }
                }
                $start=$end;
                $unknow=[];
            }
        }
        foreach($unknow as $unknown_node){
            $unknown_node->x = ($unknown_node->index - $start->index) * $this->min_space + $start->x;
        }
    }
    public function fetch_line($from,$to,$fy,$ty)
    {
        $fx=$from->x + $this->xo;
        $tx=$to->x + $this->xo;
        $this->line_svg.='<line x1="'.$fx.'" y1="'.$fy.'" x2="'.$tx.'" y2="'.$ty.'" '.$this->line_postfix;
        $this->fetch_node($to,$ty);
    }
    public function fetch_node($node,$y)
    {
        $x=$node->x + $this->xo;
        $this->node_svg.='<circle cx="'.$x.'" cy="'.$y.'" '.$this->node_postfix;
        $this->text_svg.='<text x="'.($x + $this->text_x).'" y="'.($y + $this->text_y).'" fill="red" debug="floor:'.$node->floor.';index:'.$node->index.'">'.$node->data.'</text>';

        $ty = $y + $this->floor_height;
        if($node->left !== null) $this->fetch_line($node,$node->left,$y,$ty);
        if($node->right !== null) $this->fetch_line($node,$node->right,$y,$ty);
    }
}



